ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group96a.txt/000073_icon-group-sender _Wed Apr 10 13:44:12 1996.msg

Internet Message Format | 1996-09-05 | 4KB

Received: by cheltenham.cs.arizona.edu; Wed, 10 Apr 1996 12:36:38 MST
To: [e-mail]
Date: 10 Apr 1996 13:44:12 GMT
From: [e-mail] (Marc Espie)
Message-Id: <4kgdvc$[e-mail]>
Organization: Ecole Normale Superieure, Paris
Sender: [e-mail]
References: <4kgc8d$[e-mail]>
Subject: Re: How to think about Icon?
Errors-To: [e-mail]
Status: O

In article <4kgc8d$[e-mail]>,
Peter Seebach <[e-mail]> wrote:
>I've made periodic stabs at learning icon for some time now, and I've
>come to the conclusion that it's completely unlike the languages I've
>learned previously.  In particular, I have no good mental model for
>backtracking, so I get confused by programs which do it.  This makes Icon
>hard for me to take advantage of.  :)
>
>What kind of conceptual model do you use for programming in Icon?  How
>do you use it differently from "simple" procedural languages, like C
>or Perl?
>
I don't know how it works for other people, but `iterator' is the key for me.
The classical problem that is difficult to work in other languages is
graph traversal.

In C, you usually will code a given graph traversal algorithm that takes
a call back function as a parameter---this call back will be called with each
vertex you encounter. In Icon, you will design a generator that suspends every
vertex you encounter. Up to the calling program to decide what to do with
the vertex.

This goes farther than it seems. For instance, I usually don't hardcode
my definition of a graph, but use a generator that gives me the neighbors
of a given neighbor instead.

Sample Connected Component program (this is what I actually use in practice):

procedure build_cc(v, neighors, para, cc)
    local todo

    todo := [v]
    /cc := set()    # initialize set if needed
    insert(cc, v)    # cc initially holds v
    while v := pop(todo) do
        every neighbor := neighbors(v, para) do
            member(cc, neighbor) | (insert(cc, neighbor) & put(todo, neighbor))
    return cc
end

As far as backtracking goes, the sanest way is perhaps to just consider it
as a kind of shorthand (at first): all the logical structure and all the
C variables are there, you just don't have to write it down explicitly, i.e.,
going from
    every i:= 1 to 10 do
        write(i)
to
    every write(1 to 10)
or
    if (i = 0)  | (i = 1)
to
    if i = (0|1)
isn't that difficult.

Then you can go farther to recursive generators and such intricate stuff.
This is the same conceptual leap as recursive invariants in functional
languages. The only thing you have to watch for is the precise semantics
of failure/multiple success... If I counted all the times I had a generator
resume on me when I wasn't expecting it, reverse the first result, and
finally fail---\1 is very handy at times, or all these procedural functions
that forgot to return anything and just failed, simply !

Another fun example: this one generates all permutations of a given list,
and is quite nice to understand generator resumption.

procedure do_permute(l, i, n)
    if i >= n then
        return l
    else
        suspend l[i to n] <-> l[i] & do_permute(l, i+1, n)
end

procedure permute(l)
    suspend do_permute(l, 1, *l)
end

I should add that, again, this is a real life example. Icon code tends to
be very compact, elegant, and not so easy to understand at times :-)

If you haven't already, go out and buy the Icon programming language book,
by Griswold. This is a very nice book, that gives lots of applications of
the generator/backtracking paradigm.



--
[nosave]<http://www.eleves.ens.fr:8080/home/espie/index.html>
microsoft network is EXPLICITLY forbidden to redistribute this message.
`Moon purismu powa, make up.... Tsuki ni kawatte, oshiokiyo !'
    Marc Espie ([e-mail])